Algoritma greedy adalah pendekatan yang mengambil keputusan terbaik pada setiap langkah tanpa mempertimbangkan konsekuensi jangka panjang. Strategi ini cepat dan mudah ditulis, tetapi hanya memberikan solusi optimal jika masalahnya memenuhi syarat tertentu. Banyak pemula memakai greedy untuk kasus yang sebenarnya butuh pemrograman dinamis.
Pembahasan ini mencakup cara kerja algoritma greedy, ciri masalah yang cocok, contoh penerapan, serta risiko penggunaannya. Fokusnya pada pemahaman konsep, bukan menghafal kode.
Cara Kerja Algoritma Greedy
Algoritma greedy membangun solusi selangkah demi selangkah. Di setiap langkah, ia memilih opsi yang paling menguntungkan saat itu, lalu tidak meninjau ulang pilihan tersebut. Karena tidak ada backtracking, algoritma ini biasanya berjalan cepat, sering kali dalam kompleksitas polinomial.
Contoh sederhana: menukar koin dengan pecahan 25, 10, 5, dan 1. Untuk 63 sen, greedy memilih 25+25+10+1+1+1, total 6 koin. Apakah ini optimal? Untuk pecahan tersebut, ya. Tetapi jika pecahannya 1, 3, 4 dan target 6, greedy memilih 4+1+1 (3 koin) padahal solusi optimal adalah 3+3 (2 koin). Di sinilah kelemahan greedy muncul.
Jadi, greedy hanya tepat untuk masalah yang memiliki dua sifat: greedy-choice property dan optimal substructure. Sifat pertama berarti pilihan terbaik lokal bisa membawa ke solusi global terbaik. Sifat kedua berarti solusi optimal masalah besar terdiri dari solusi optimal submasalah.
Contoh Masalah yang Cocok untuk Greedy
Beberapa masalah klasik memang dirancang agar greedy bekerja optimal. Berikut tiga di antaranya:
- Activity selection: memilih sebanyak mungkin aktivitas yang tidak tumpang tindih. Strategi greedy: urutkan berdasarkan waktu selesai, lalu ambil yang paling awal selesai.
- Huffman coding: membangun pohon biner dengan menggabungkan dua simpul berfrekuensi terendah secara berulang.
- Minimum spanning tree (algoritma Kruskal dan Prim): menambahkan sisi termurah yang tidak membentuk siklus.
Untuk masalah graph seperti mencari jalur terpendek, greedy saja tidak cukup. Algoritma Dijkstra memakai strategi greedy dengan batasan bobot tidak negatif, dan penjelasan langkah demi langkahnya bisa dibaca di panduan menerapkan algoritma Dijkstra. Memahami perbedaan keduanya membantu memilih alat yang tepat.
Kapan Greedy Gagal
Greedy gagal ketika keputusan lokal yang tampak menguntungkan justru menghalangi solusi yang lebih baik di kemudian hari. Masalah knapsack 0/1 adalah contoh klasik. Jika kita memilih barang dengan rasio nilai/berat tertinggi terlebih dahulu, hasilnya bisa tidak optimal karena sisa kapasitas tidak terpakai efisien.
Contoh lain adalah mencari jalur dengan biaya terkecil pada graph yang memiliki sisi negatif. Greedy bisa terjebak di jalur yang tampak murah di awal tetapi berujung mahal. Untuk kasus seperti ini, pemrograman dinamis atau algoritma Bellman-Ford lebih tepat.
Sebelum menerapkan greedy, uji dengan contoh kecil. Apakah ada kasus di mana pilihan pertama yang terbaik justru membuat langkah berikutnya mustahil? Jika ya, greedy bukan pilihan yang aman. Membandingkan struktur data yang sesuai juga penting; lihat perbandingan struktur data untuk belajar algoritma.
Membuktikan Kebenaran Greedy
Menulis kode greedy itu singkat. Yang sulit adalah membuktikan bahwa algoritma tersebut selalu menghasilkan solusi optimal. Ada dua teknik pembuktian yang umum dipakai:
- Exchange argument: andaikan ada solusi optimal yang berbeda dari solusi greedy. Tunjukkan bahwa kita bisa menukar satu elemen tanpa memperburuk solusi, sehingga solusi optimal bisa diubah menjadi solusi greedy.
- Stays-ahead: bandingkan solusi greedy dengan solusi optimal langkah demi langkah. Tunjukkan bahwa greedy tidak pernah tertinggal.
Keduanya memerlukan pemahaman sifat masalah, bukan sekadar intuisi. Di soal coding interview, pewawancara sering meminta argumen singkat mengapa greedy valid. Latihan membaca pseudocode dan membangun argumen seperti ini bisa diasah lewat perbandingan metode latihan algoritma.
Greedy dalam Kehidupan Sehari-hari Pemrogram
Di luar soal algoritma, pola greedy muncul di banyak keputusan teknis. Contohnya, sistem cache yang menyimpan data paling sering diakses, penjadwalan tugas dengan deadline terdekat, atau kompresi data. Namun, keputusan greedy pada sistem produksi sering kali perlu dimodifikasi dengan heuristik karena kondisi nyata tidak sesederhana asumsi teori.
Dalam pengembangan web, prinsip serupa juga terlihat saat menata antarmuka. Memilih label dan placeholder yang tepat adalah keputusan kecil yang berdampak pada usability; ulasan praktisnya ada di tips menata label dan placeholder formulir. Sementara itu, untuk animasi sederhana yang tidak mengganggu performa, pola jQuery sering dipakai sebagai solusi cepat; baca tips jQuery untuk pemula.
Kembali ke algoritma, kunci penggunaan greedy adalah kesadaran akan batasnya. Jangan langsung menerapkan greedy hanya karena kodenya pendek. Pastikan dulu masalahnya memenuhi syarat, atau setidaknya uji dengan beberapa kasus ekstrem.
Ringkasan
Algoritma greedy memilih opsi terbaik di setiap langkah tanpa menoleh ke belakang. Ia efisien dan mudah diimplementasikan, tetapi hanya optimal untuk masalah dengan greedy-choice property dan optimal substructure. Ketika ragu, bandingkan dengan pendekatan lain seperti pemrograman dinamis atau exhaustive search untuk memastikan kebenarannya.
Pertanyaan yang Sering Diajukan
Apakah algoritma greedy selalu memberikan solusi terbaik?
Tidak. Greedy hanya optimal pada masalah yang memenuhi syarat tertentu. Untuk banyak masalah, greedy memberi solusi yang cukup baik tetapi bukan yang terbaik.
Bagaimana cara mengetahui suatu masalah cocok untuk greedy?
Periksa apakah masalah memiliki greedy-choice property dan optimal substructure. Cara praktisnya, coba cari counterexample dengan contoh kecil. Jika tidak ada dan secara intuitif pilihan lokal selalu konsisten, kemungkinan greedy bisa dipakai, tetapi tetap perlu pembuktian formal.
Apa perbedaan utama greedy dan pemrograman dinamis?
Greedy membuat keputusan sekali dan tidak meninjaunya, sedangkan pemrograman dinamis menyimpan hasil submasalah dan mengeksplorasi kombinasi keputusan. Greedy lebih cepat tetapi kurang fleksibel.